Game Theory (L11)

Coverage outline

NS: chapter 5 (nearly all of it, see web book)

  • Additional to text: Dominance, rationalizability

  • Experimental evidence (and evidence from the real world); supplements

… Problem set coming, heavy coverage of game theory!

Module context

  1. Basic tools, the economic approach

  2. The simple classical model, welfare results

  1. Market failures (Monopoly, Public Goods)


  1. Extensions of simple model: ‘Die roll’ Uncertainty

\(\rightarrow\) and now Strategic uncertainty \(\rightarrow\) Game Theory

Is game theory useful???

Some people seem to think so:


Today:

  1. How economists consider strategic interaction. What’s game theory and who cares?


  1. How to illustrate games; ‘Notation & grammar’


  1. Prisoners’ Dilemma example


  1. Some key concepts, predictions: Common Knowledge, Dominant/dominated strategies, ISD/Rationalisability…

Please have Turningpoint/Responseware available over next lectures

Basic concepts (strategic interaction, elements of a game)

Previously: Each individual (consumer, firm… ) takes others’ choices as given

  • market price, demand curve, etc.


Now: Consider strategic interaction

My best choice may depend on your choice, & vice versa


  • Sequential games: My earlier choices may change your later choices

One minute exercise


Find a situation—in business, government, fiction, history or your own life—

… where one party’s optimal choice depends on what another party does.


Write it down, give 1-sentence explanation of why it involves ‘strategic dependence’

Some possible examples:

  • Ask out your crush or not?
  • Country makes war or peace? Soldiers fight or run away?


  • Run for office or not? Party contests a seat? If so, how much to spend on campaign?


  • Amount to bid at a first-price auction?

  • Whether Robotic Chef opens a new branch in Exeter, and where?

  • How hard to work towards a promotion at your job?

##Some examples

Is it better to get lunch at Comida or Pret?


What if your friends are going to Comida?


What if everyone and her cousin are going to Comida, so the queue is miles long?

What should Tim Cook charge for his new Iphone?


Does it depend on whether Samsung and LG…

… Sell their phones for £200, or £1000, or go out of business?

What game theory can do (wet blanket)

A language & framework for analyzing strategic situations


  • Solution concepts make predictions under given assumptions

  • Equilibrium defined as a baseline

Four elements describe a game

Four elements describe a game

  1. Players

  2. Strategies

  3. Payoffs

  4. Information

Players

the decision makers in the game


\(2, 3, . . . , N\) players


Who are the players in the game ‘Chicken?’

Strategies
a player’s choices at each ‘decision node’ of the game

Simple games: same as actions

Payoffs

Each player’s utility from the combination of each player’s strategies (and chance) in the game

  • May include ‘money earned’ + other considerations; all summarised in the payoff numbers

  • Each player’s goal: maximise her payoff (not just to ‘win’)

Payoffs in chicken?
  • Both pull-off \(\rightarrow\) Tie
  • N Straight, S pulls off \(\rightarrow\) N ‘wins’, S ‘loses’

  • N pulls off, S straight \(\rightarrow\) N ‘loses’, S ‘wins’

  • Both straight \(\rightarrow\) crash

To convey this game payoffs must follow: Win \(\succ\) tie \(\succ\) lose \(\succ\) crash

Example of payoffs in Chicken (as matrix)

Information

what each player knows, at a particular point in the game, about payoffs and previous actions

For sequential games, players may or may not know other players’ previous actions

Consider… for the game you imagined earlier…


  • Who are the players

  • What are the actions/strategies

  • What are the payoffs?

  • Is it simultaneous or sequential?

Illustrating Games

The Prisoners’ dilemma

The Prisoners’ Dilemma: Normal form

Vote: A - confess, B - Silent

Vote: A - confess, B - Silent

Q1: What would you do?

Q2: What do you think game theory predicts people will do?

Q4: Which outcome is definitely NOT Pareto-optimal (for the prisoners)?


  • A. Both players confess

  • B. Both players are silent

  • C. A confesses and B is silent

  • D. B confesses and A is silent

  • E. All outcomes may be Pareto-optimal

A Prisoner’s Dilemma be like


Two Players: (A and B, row and column, whatever)


Strategies (Actions): ‘Cooperate’ with other prisoner (C) or defect (D) and confess


In normal form:

In normal form:


To be a prisoner’s dilemma, payoffs must satisfy \(T > R > P > S\)

  • Temptation \(>\) Reward \(>\) Punishment \(>\) Sucker

Common knowledge

  • What all players know, and
  • all players know that all other players know,
  • and all players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know,
  • and all players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know that all other players know,
  • etc.

Why is common knowledge important?

You may be stuck on an island with 100 blue-eyed people and 900 brown-eyed people

(Links to video and cartoon versions in handout)

  • Warning: puzzle will do your head in

Island with 1000 people. 100 w/ blue eyes, 900 brown eyes. No reflective surfaces.

By strict custom:

American tourist says ‘It’s so nice to see one or more people with blue eyes in this part of the world’.


Q: What effect, if any, does this faux pas have on the island?

GT predicts: Statement made common knowledge \(\rightarrow\) all 100 blue-eyed suicides 100 days later

A’s Best Response (BR) to strategy S:

a strategy for player A that gives him the highest payoff of all his possible strategies, given that the other player(s) play S

Dominant, dominated strategies and rationalizability

Dominant, dominated strategies and rationalizability

Dominant strategy
A single strategy that is a best response to any of the other player’s strategies.

Simple prediction: a ‘rational’ player will play a dominant strategy if she has one.


Dominated strategy
Strategy A is dominated by strategy B if B yields higher payoffs for any of the other player’s strategies

A simple prediction: a rational player will never play a dominated strategy

Prediction of ‘players play dominant strategies’


…in Prisoner’s dilemma?

But in other cases, this may have no clear prediction

Rationalisability/ Iterated strict dominance

Extending this …


Rationality assumption: the players are rational

  • We know rational players won’t play dominated strategies
  • The players themselves know this

Common Knowledge of Rationality assumption:

Players know all other players are rational. They know all players know all players are rational. They know… (all players know … ad infinitum) … all are rational.


Thus they know other players will never play a dominated strategy, and eliminate these from consideration.

Thus they won’t play a strategy if another strategy is always better against this reduced set of possibilities.

…Etc.


… the process of ‘Iterated Strict Dominance’ (ISD). \(\rightarrow\) Strategies that survive ISD: ‘rationalizable’

ISD example; may yield a unique prediction

But there may be no dominated strategies, or ISD may leave many possibilities

TIL

  1. How economists consider strategic interaction

  2. Basic notation & grammar of game theory


  1. What defines a “Prisoners’ Dilemma”


  1. Key concept: Common Knowledge

  2. Predictions: Dominant/dominated strategies, ISD/Rationalisability

Second game theory chunk: coverage

Second game theory chunk: coverage

  1. Equilibrium and Nash Equilibrium: definition, finding NE in matrix games (some examples)


  1. Pure and Mixed strategies (Mixed strategies: get the basic concept, no need to compute these)

  1. Multiple equilibria and refinements


  1. Sequential Games (and extensive form)


  1. Repeated games: definite time horizon; indefinite/infinite

  2. Repeated games: indefinite/infinite


  1. Continuous Action games

  2. Experimental evidence: What is a laboratory experiment in Economics?

Equilibrium

Equilibrium

Market equilibrium (recapping): given the equilibrium price & quantity, no market participant has an incentive to change her behaviour.



Similar concept for strategic settings:

Nash equilibrium (NE)
A set of strategies, one for each player, that are best responses against one another
Nash equilibrium (NE)
A set of strategies, one for each player, that are best responses against one another

If I play my BR to your chosen strategy and you’re playing your BR to mine, neither of us has an incentive to deviate — an equilibrium.

All games have at least one Nash equilibrium

  • But it may be an equilibrium in ‘mixed strategies’ (involving randomisation)

Caveat: we might not expect such play to actually occur (particularly not in one-shot games)

Two ways to find the Nash equilibrium (NE)

First method: Inspection

Check each outcome.


Either player has incentive to unilaterally deviate?


If not \(\rightarrow\) it’s (outcome of) a NE.

Second method to find NE – Underlining


Underline payoffs for BR’s of each player.


Outcome with 2 underlines \(\rightarrow\) outcome of a NE (strat. profile).

Find equilibrium via each method:

Relationship between dominant strategies, rationalisability, and Nash equilibrium

If eliminating dominated strategies yields a single prediction for each player, these form a NE (profile).


Same for ISD (rationalizability) … if it leads to a unique prediction, it’s a NE.


HOWEVER: not every NE involves dominant strategies

Coordination and anti-coordination games

In-class experiment: BOS & coordination; need 2 volunteers

Coordination: Battle of the sexes (BOS)

Anti-coordination: Matching pennies (odds/evens)

Mixed strategies

Mixed strategies

2019-20: know the basic principles; you don’t need to compute mixed strategies

Pure strategy
Consists of a single action played with certainty
Mixed strategy
Assigns a probability to each possible action

Remember: there is always at least one NE. If there is no pure strategy NE, there will be a NE in mixed strategies.

Matching pennies: mixed strategies

Intuition

  • If you choose heads/tails half the time then I’m indifferent between heads or tails
    • choosing heads half the time is among my best responses


  • If I choose heads half the time then you’re indifferent between heads/tails
    • choosing heads half the time is among your best responses


  • So, technically, each of us choosing heads half the time is a NE

Battle of sexes: mixed strategies

Want to derive the best response functions, find intersections.

Let \(h\): probability husband chooses Ballet, \(w\): probability wife chooses Ballet

Rem: Wife chooses Ballet (Box) \(\rightarrow\) Husband’s BR is Ballet (Box)

Using ‘EU’: Compute Husb’s payoff from playing Ballet & from Boxing if Wife chooses Ballet w/ prob. w

\(\rightarrow\) ‘Threshold’ prob. \(\bar{w}\) makes him indifferent; for \(w<\bar{w}\) , he chooses Box; for \(w >\bar{w}\) he chooses Ballet.


… similarly, wife indifferent btwn her 2 choices for some prob. \(\bar{h}\); for \(h<\bar{h}\), she chooses Box, for \(h>\bar{h}\) she chooses Ballet.

Wife goes Ballet if thinks husband goes Ballet \(>\) 1/3 of time

If she thinks he goes below 1/3 of the time she goes Boxing

If she thinks he goes exactly 1/3 of the time she is indifferent

Nash equilibria where BRF meet

Three equilibria: both Boxing, both Ballet, mixed strategy; are any more reasonable as predicted outcomes?


Also see further discussion in handout about whether and why a mixed strategy equilibrium is a reasonable prediction, and what the intuition is.

How do you solve a problem like multiple-equilibria? (WIP)

Backing track

There’s always one or more they say but sometimes it is mixed
you find one where the best responses meet at some point fixed
you only know you won’t regret the strategies it ‘picksed’
I hear that it’s prediction power is shabby


It might not yield the best outcome and might not yield the worst
In prisoner’s dillemas a confession is coerced,
I hate to have to say it, but I very firmly feel Nash Equilibrium’s not an asset to the abbey

I have to say a word on its behalf: multiple-equilibria make me laugh

So,

How do you solve a problem like multiple-equilibria?

  • How do you catch a cloud and pin it down?
    • How do choose among the multiple-equilibria?
    • A flibbertjibbet! A will-o’-the wisp! A clown!

Many a thing you’d like old Nash to tell you
Many a thing you thought you’d understand
But how do you find a way to predict equilibrium play?
How do you keep a wave upon the sand?

Oh, how do you solve a problem like multiple-equilibria?
How do you hold a moonbeam in your hand?

‘The Big Game’

A previous year’s results (2016, with slightly different payoffs)

Share chose .. squared Pay if match E(Pay)
1 0.26 .068 2 0.52
2 0.21 .044 2 .42
3 0.11 .012 1 .11
4 0.16 .026 2 .32
5 0.26 .068 2 .52
Wtd avg 0.22 0.05 0.42


In this trial the ‘middle square’ yielded payoffs of 1

Multiple equilibrium and refinements

Multiple equilibrium and refinements

We refer to refinement criteria and focal points

Equilibrium with the highest payoffs for both?

  • In BOS this rules out mixing (payoffs 2/3, 2/3 for h,w respectively)

  • But doesn’t say whether it’s Box, Box (payoffs 2,1) or Ballet, Ballet (payoffs 1,2)


Choose the ‘symmetric equilibrium?’ … here, mixing

Choose the one that seems like a ‘focal point’? (rem, the ‘big game’)

Is there a focal point?

A year after graduating you come back for Alumni Weekend. You are supposed to meet the veterans of this module for a night of festivities but can’t remember where or when.

The internet does not exist.

Where do you go? Write it down on a piece of paper

  • Now type what you wrote in to the chat window

What if you are meeting for a reunion in London, and no one has internet or phone access?

  • Where do you go?

  • Write it down

  • Type it into the chat window.

Refinements are real-

(ly) important to some academic referees:

However, I am dismayed that you chose to ignore my suggestion to come up ”with a reasonable refinement that kills all C-F equilibria." I agree that introducing additional types and rounds may smooth out the extreme outcome in the C-F equilibria. But, it is perfectly fair to evaluate the predictions of your actual model and it does not include these features.

Sequential Games (and extensive form)

Sequential Games (and extensive form)

Consider Battle of Sexes, but now Wife chooses first, Husband observes this and then chooses. What do you think will happen? Vote:

A. Wife: Ballet, Husband: Box

B. Wife: Ballet, Husband: Ballet

C. Wife: Box, Husband: Ballet

D. Wife: Box, Husband: Box

  • The wife has two strategies: Ballet or Boxing
  • The husband has four contingent strategies, but we focus on what he will do in each of his two possible ‘decision nodes’

Proper subgame
Part of the game tree including an initial decision not connected to another (oval or dashed lines) and everything branching out below it.


I.e., each ‘game’ starting from a point where a player knows where she is (knows previous choices)

Subgame-Perfect Nash Equilibrium (SPNE)
Strategies that form a Nash equilibrium on every proper subgame.

You can solve for this with ‘backwards induction’ (BWI)

  • Solve for best move for last decision node (proper subgame)
    • Given these, solve for best response for previous decision node
    • Etc.
  • State the complete contingent strategies suggested by this

Example: BWI for BOS

Formally specify (SP)NE strategies for above game:

a NE, not SP: {Wife: Boxing; Husband: Boxing, Boxing}

SPNE: {Wife: Ballet; Husband: Ballet, Boxing}

(reading Husband’s decision nodes left to right; please specify this)

It can get fancier

In ‘normal’ (matrix form), stating complete contingent strategies:

Find the SPNE; ‘state the complete contingent strategies’

A: S1, N3, N5

B: s2, n4, n6

Repeated games: definite time horizon

Repeated games: definite time horizon

A ‘stage game’ is a simple (matrix) game that may be played repeatedly

  • Definite horizon: play stage game a known and finite number of times

Note: In repeated (as in sequential) games, a strategy is a ‘complete contingent plan’; specifies what the player will choose at every decision node

A general rule for (finitely) repeated games

Whenever the stage-game is repeated, repeated play of the stage-game equilibrium is an equilibrium of this repeated game

  • In a finitely-repeated Prisoner’s dilemma this is the only equilibrium

Is there a way in which we can sustain cooperation in a finitely repeated Prisoners’ Dilemma?


No.

Suppose we repeat the Prisoners’ Dilemma a finite (T) number of times, e.g., 10 times.

What is the subgame perfect equilibrium?


Backwards induction:

  • In period 10 (period T) both confess as it’s the dominant strategy
  • In period 9 (period T-1)
    • Knowing period 10 (period T) decision is unaffected by earlier moves, players confess in period 9 (their dominant strategy)
  • … etc, all the way back to period 1

Thus each Confesses in every period \(\rightarrow\) Can’t sustain cooperation.

Repeated Games: Indefinite or infinite

Repeated Games: Indefinite or infinite time horizon (mathematically equivalent)

Game played repeatedly for potentially infinite number of periods


  • But there is a ‘discount factor’ \(g\)


  • \(g\) may instead represent ‘probability the game is repeated another time’

Trigger strategies

Trigger strategy
Strategy in a repeated game where one player stops cooperating in order to punish another player for not cooperating.


Grim trigger strategy
If other player fails to cooperate in one period, play the (undominated) strategy that makes the other player worst off in all later periods

Indefinitely repeated Prisoners’ Dilemma

Consider the following trigger strategy (for both players):

  • Stay silent as long as the other player stays silent.
  • If one player confesses, both players will confess from them on.

Is this a SPNE?

  • In each subgame after someone confesses, we play confess in all stage games (forever on), which we know is a NE
  • What about periods where no one has confessed (yet)?

The payoff from staying Silent (cooperating) each period is:

\[-2 \times (1 + g + g^2 + g^3 + . . . )\]


The payoff from Confessing right away (after which both players Confess always) is:

\[ -1 + -3 \times (g + g^2 + g^3 + . . . ) \]


Formula for a geometric series (where \(0<g<1\)): \[g + g^2 + g^3 + g^4 ... = g/(1-g)\]

Thus cooperation in a single period is ‘weakly preferred’ (at least as good) if

\[(-2) \times (1 + g + g^2 + g^3 + . . . ) \geq (-1) + -3 \times (g + g^2 + g^3 + . . .)\]

\[g + g^2 + g^3 + . . . \geq 1\]

\[\frac{g}{1-g} \geq 1\]

\[g \geq \frac{1}{2}\]

\(\rightarrow\) cooperation can be sustained if the ‘probability of play continuing’ (or ‘patience’) is high enough; here, above 1/2.

Continuous Actions

Continuous Actions

GT for cases where people choose ‘continuous’ actions, e.g.:


  • Firms choose product price or quantity, or a level of R & D, etc.


  • Households voluntarily contribute to local public good (e.g., neighborhood watch)
    • or choose how many fish to catch from the shared pond


  • Nations: How large an army to build

With continuous actions…


\(\rightarrow\) Payoff functions, continuous ‘best response functions’; rather than a payoff matrix


  • Nash equilibrium: Again, choices that are best responses to one another


  • Dominant strategies: Again, a strategy that is preferred against any other player(s)’ strategies

Continuous games with differentiable payoffs, finding NE:

  1. Write down payoff functions. (Differentiable?)

  2. Max each player’s payoff wrt own strategy; other player’s payoff as a ‘parameter’ \(\rightarrow\) Players’ best-response functions.

  3. Look for intersection(s) \(\rightarrow\) Nash equilibrium/equilibria

Tragedy of the Commons

Shepherds A & B graze \(s_A\) & \(s_B\) sheep, respectively, in same meadow

More sheep graze \(\rightarrow\) less grass for each \(\rightarrow\) less wool/milk/meat per sheep

Benefit per sheep raised: \(120-s_A-s_B\)


Total benefit from raising \(s_A\) and \(s_B\) sheep:

  • Shepherd A: \(s_A(120-s_A-s_B)\)
  • Shepherd B: \(s_B(120-s_A-s_B)\)


Marginal benefit of ‘me adding’ another sheep:

  • Shepherd A: \(120-2s_A-s_B\)
  • Shepherd B: \(120-s_A-2s_B\)

For simplicity, assume zero marginal cost


Set MB=MC (here MC=0)

  • Shepherd A: \(120-2s_A-s_B = 0\)
  • Shepherd B: \(120-s_A-2s_B = 0\)


Rearrange above to solve for BRFs:

  • Shepherd A: \(s_A = 60-\frac{1}{2} s_B\)
  • Shepherd B: \(s_B = 60-\frac{1}{2} s_A\)

Solve for Nash equilibrium:

\[s_A = 60-\frac{1}{2} s_B\]

Plug this value of \(s_A\) into the BRF for B, solve for \(s_B\), then for \(s_A\)

\[s_B = 60-\frac{1}{2} s_A = 60 - \frac{1}{2}(60-\frac{1}{2} s_B)\]

\(s_A* = s_B* = 40\)

Shepherd A: \(s_A = 60-\frac{1}{2} s_B\)


Shepherd B: \(s_B = 60-\frac{1}{2} s_A\)


\(\rightarrow s_A* = s_B* = 40\)

Why the ‘Tragedy’ of the Commons?

Each grazes until his private marginal benefit equals his cost (0):

\(120-2s_A-s_B = 0\)

Does not consider the harm he imposes on the other guy

Above solves to \(s_A^{*} = s_B^{*} = 40\).

Each get payoff \(40 \times (120 - 40 - 40) = 40 \times 40 = 1600\)


To max total payoffs, set \(S=s_A+s_B\) to max

\[S\times(120-S)\]

Concave problem, set first-derivative to zero: \[120 - 2S = 0 \rightarrow S^*=60\]

Leading to total payoff \(60 \times (120 - 60) = 3600\). If split evenly (each graze 30), get 1800 each.

Sadly, this problem (literally!) is still relevant

Experimental evidence: What is a laboratory experiment in Economics?

Experimental evidence: What is a laboratory experiment in Economics?

E.g., FEELE lab at Exeter

  • Real incentives (typically small)
  • Typically student subject pool
  • No deception protocol

Various experimental goals

  • Measure preferences (risk, time, social preferences…)
  • Asses theoretical predictions (classical and behavioural), including game theory
    • Also see ‘likely’ outcomes where theory has no prediction or predicts multiple equilibria
    • Critical to assert ‘control’ over payoffs for this
  • Understand cognitive processes in economic realm
  • ‘Test’ institutions and mechanisms (e.g., auctions, markets)

Laboratory evidence 1: Prisoners’ dilemmas

Cooper et al (1996)

Cooperation even in anonymous ‘1-shot’ games (different opponents each time)

Cooperation declines somewhat over time, but not to zero

Mix of other-regarding and selfish types

Laboratory evidence 2: Ultimatum game

Proposer goes first, proposes split of the ‘pie’, anything between 0%-100% and 100%-0% inclusive.


Responder can accept, or reject and get nothing

What happens in experiments?

  • Most common offer: 50-50 split
  • Responders: Often reject offers of less than 30% (even when it’s a lot of money)

Potential explanations

  • Fairness concerns; monetary payoffs may not be actual payoffs
  • Proposers may anticipate this

Issues in lab experiments

What is being measured?

PD: Does money measure the true payoffs? Do we have the ‘control’ to test the model?

  • Other-regarding preferences; may be unobservable.
  • ‘Experimenter demand’: desire to please experimenter, aware of study goals?

Issues in lab experiments: External generalisability

  1. Relevance of subject-pool (participants)
  • Do they resemble the ‘real world’ group of interest? (e.g., firms, countries, taxpayers, voters, home-buyers)

  • Right preferences and experience?

  1. Relevance of environment
  • Are the (small) stakes relevant?

  • Are the right ‘environmental characteristics’ present?

  • Does the ‘imposed model’ apply?

  • Observed self-conscious environment, perhaps made aware of contrasts

Suggested practice problems: see VLE